BZOJ 1025 游戏

Description

windy学会了一种游戏。对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。 如: 1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6 windy的操作如下 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2 3 4 5 6 这时,我们就有若干排1到N的排列,上例中有7排。现在windy想知道,对于所有可能的对应关系,有多少种可能的排数。

Input

包含一个整数,N。

Output

包含一个整数,可能的排数。

Sample Input

【输入样例一】
3
【输入样例二】
10

Sample Output

【输出样例一】
3
【输出样例二】
16

Hint

【数据规模和约定】
100%的数据,满足 1 <= N <= 1000 。

Solution

有一点置换的知识就知道是求一个lcm
然而着并没有什么卵用= =
这些置换是不知道的,唯一的条件是a1+a2+a3+……=n
但是这个lcm可以分解一下质因数
lcm=p1^k1*p2^k2……
然后可以知道素数是小于等与n的
那么用一个f[i][j]表示前i个素数,和为j的方案数
由于每种选法都一定单独对应一个lcm,所以答案应该是背包方案数
但是lcm里面是没有考虑1的,而1在和之中是可以算贡献的,那么小于等于n的全部加进来就是答案

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

#define maxn 1000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

ll f[maxn][maxn],ans;
int prime[maxn],pri[maxn],tot;
int n;

void get()
{

for(int i=2;i<=n;i++){
if( !prime[i] ) pri[++tot]=i;
int j=1;
while( j<=tot && pri[j]*i<=n ){
prime[pri[j]*i]=1;
if( i%pri[j]==0 ) break;
j++;
}
}
}

void DP()
{

f[0][0]=1;
for(int i=1;i<=tot;i++){
for(int k=0;k<=n;k++)
f[i][k]=f[i-1][k];
for(int j=pri[i];j<=n;j*=pri[i])
for(int k=0;k<=n-j;k++)
f[i][k+j]+=f[i-1][k];
}
for(int i=0;i<=n;i++)
ans+=f[tot][i];
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1025.in","r",stdin);
freopen("1025.out","w",stdout);
#endif
scanf("%d",&n);
get();
DP();
printf("%lld",ans);
return 0;
}